o problema foarte interesanta. de ce? pentru ca se poate rezolva
usor folosind programare dinamica si se aseamana cu o problema
care nu poate fi rezolvata de algoritmi. (Post correspondence
problem aka PCP)

ideea de programare dinamica este simpla, pt fiecare cuvant, ti
un vector de aceeasi marime, v_a[i] reprezinta cel mai mic index
astfel incat poti sa scrii un cuvant care sa poata fi scris
pana la index v_a[i] de cuvinte din B si pana la index v_a[i]-i
cu cuvinte din A si "sub"-cuvantul a[1..i] se poate adauga la fix.
la algoritmul exact te las pe tine sa te gandeshti ca sa nu iti
stric distractia.

in PCP ai dominouri de tipul:

[a]
---
[ab]

si trebuie sa le concatenezi si sa ajungi la acelasi rezultat sus cat si
jos.

exemplu:
[b]     [a]    [ca]    [abc]
----    ---    ----    -----
[ca]    [ab]   [a]     [c]

o solutie este:

[a][b][ca][a][abc]
[ab][ca][a][ab][c]

problema asta este "undecidable." se poate demonstra folosind o
tehnica numita "computation histories" O alta problema undecidable
foarte cunoscuta este "halting problem" - adica detectarea a unui
program daca se blocheaza (cicleaza la infinit) sau nu.

ah, btw, de obicei este mult mai nasol sa ai o conditie intr-o
problema de tipul "foloseshte x numai o singura data" decat
"foloseshte x de oricate ori" exemplu: drumul maxim intr-un graf.... 
hehe, daca poti sa foloseshti un arc de oricate ori problema e simpla,
daca nu, e NP-completa. ah, si de obicei cand ai conditii de tipul
de care ai vrut tu, programarea dinamica nu mai tine... incearca sa
pui conditii de tipul ala in probleme pe care le stii sa le faci
cu dinamica si vezi ce se intampla.

--mihai
>
>PROBLEMA
>---------
>
>	Se dau 2 colectii de cuvinte, A si B. Fiecare
>colectie poate contine maxim 100 de cuvinte, fiecare
>cuvant avand lungimea maxima de 50 de caractere. Se cere
>sa se determine un sir de caractere de lungime minima,
>care sa se poata scrie ca o concatenare a unor cuvinte din
>A (fiecare cuvant poate sa apara de mai multe ori), cat si
>ca o concatenare a unor cuvinte din B (fiecare cuvant din
>B poate sa apara de mai multe ori). In caz ca nu exista un
>astfel de sir, se va tipari 0. In caz ca exista, se va
>tipari lungimea acestuia (care, dupa cum am spus, trebuie
>sa fie minima posibila).
>
>EXEMPLU:
>-COLECTIA A-
>ABC
>CB
>-COLECTIA B-
>CBA
>BC
>
>	Sirul S cautat este CBABC si are lungimea 5.
>S=CB+ABC (concatenarea unor cuvinte din A)
>S=CBA+BC (concatenarea unor cuvinte din B)
>
>	Mie mi se pare o problema destul de dificila,
>avand in vedere ca fiecare cuvant poate sa apara de
>oricate ori,in orice "zona" a sirului S. S-ar putea
>incerca ceva de genul sa formezi toate concatenarile
>posibile ale unor cuvinte din colectia A,si sa verifici
>daca se poate forma sirul respectiv ca o concatenare a
>unor cuvinte din B,dar, intrucat un cuvant poate sa
>apara de mai multe ori, nu stim de cate ori trebuie
>folosit ca sa obtinem un sir care sa poata fi format si 
>din cuvinte din B. In plus, nu este obligatorie folosirea
>tuturor cuvintelor.
>	Sper sa aiba cineva idei mai bune...
>
>
>
>
>	Avand in vedere ca se apropie nationala, eu cred
>ca ar fi bine sa se trimita mai multe probleme pe lista,
>ca sa avem ce lucra. Asa ca daca cineva are probleme pe care
>nu stie cum sa le rezolve, sau stie, dar i se par, oricum,
>interesante, ar putea sa le trimita. Chiar daca, poate, unele
>dintre ele vor fi cunoscute, probabil se vor gasi cateva cu
>adevarat interseante. Ce parere aveti?
>	De asemenea, nu doar probleme ar putea fi trimise,
>ci si ceva algoritmi interesanti (ca,de exemplu, implementarea
>diagramelor Voronoi in N^2*logN, trimisa acum de curand --- mi
>s-a parut foarte interesanta).
>
>	De la
>	Mugurel Ionut Andreica
>
